import java.util.*;
//public class Main {
//
//import java.util.*;
//        public class Solution    {
//            /**
//             * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//             *
//             *
//             * @param str string字符串
//             * @return string字符串
//             */
//            public String setstring (String str) {
//                char[] ch = str.toCharArray();
//                char ret = ' ';
//                int kk = 0;
//                for(int i=1; i<ch.length; i++){
//                    for(int j=0; j<i; j++){
//                        if(ch[i] == ch[j]){
//                            ch[i] = ' ';
//                            for(int k=i; k<ch.length-1-kk; k++){
//                                ret = ch[i];
//                                ch[i] = ch[i+1];
//                                ch[i+1] = ret;
//                                kk++;
//                            }
//                        }
//                    }
//                }
//                String s = new String(ch);
//                return s.trim();
//            }
//        }
//
//    public static void main(String[] args) {
//        int[] a = {1 ,4 ,6};
//        int[] b = {2, 5, 9};
//        int m = a.length;
//        int n = b.length;
//        merge(a ,m, b, n);
//    }
//}


import java.util.*;
//public class Main {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param str string字符串
//     * @return string字符串
//     */
//    public static String setstring (String str) {
//// write code here
//        char[] ch = str.toCharArray();
//        char ret = ' ';
//        int kk = 0;
//        for(int i=1; i<ch.length; i++){
//            for(int j=0; j<i; j++){
//                if(ch[i] == ch[j]){
//                    ch[i] = ' ';
//                    for(int k=i; k<ch.length-1-kk; k++){
//                        ret = ch[k];
//                        ch[k] = ch[k+1];
//                        ch[k+1] = ret;
//                    }
//                    kk++;
//                }
//            }
//        }
//        String s = new String(ch);
//        return s.trim();
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        String str = scanner.nextLine();
//        System.out.println(setstring(str));
//    }
//}

//public class Main {
//    public static String setstring (String str) {
//// write code here
//        char[] ch = str.toCharArray();
//        char ret = ' ';
//        int kk = 1;
//        int qq=0;
//        for(int i=ch.length-1; i>-1; i--){
//            for(int j=0; j<ch.length-kk; j++){
//                if(ch[i] == ch[j]){
//                    ch[i] = ' ';
//                    break;
//                }else {
//                    if (qq <= i) {
//                        ret = ch[i];
//                        ch[i] = ch[qq];
//                        ch[qq] = ret;
//                        qq++;
//                    }
//                }
//            }
//            kk++;
//        }
//        String s = new String(ch);
//        return s.trim();
//    }
//
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        String str = scanner.nextLine();
//        System.out.println(setstring(str));
//    }
//}


import java.util.*;
//public class Main {
//    public void merge(int A[], int m, int B[], int n) {
//        int num = 0;
//        while (true) {
//            if (A[num] == 0) {
//                break;
//            } else {
//                num++;
//            }
//        }
//        int size2 = B.length;
//        for (int i = 0; i < size2; i++) {
//            A[num] = B[i];
//            num++;
//        }
//        int ret = 0;
//        int size1 = A.length;
//        for (int j = 0; j < size1 - 1; j++) {
//            for (int k = 0; k < size1 - 1 - j; k++) {
//                if (A[k] > A[k + 1]) {
//                    ret = A[k];
//                    A[k] = A[k + 1];
//                    A[k + 1] = ret;
//                }
//            }
//        }
//    }
//}

//public class Main {
//    public static void main(String[] args) {
//        //创建一个空的列表
//        List<Integer>list1 = new ArrayList<>();
//
//        //构造一个具有10个容量的列表
//        List<Integer>list2 = new ArrayList<>(10);
//        list2.add(1);
//        list2.add(2);
//        list2.add(3);
//        //list2.add("hello");//编译失败，List<Integer>以及限定了，list2中只能存储整型元素
//
//        //list3构造好之后，与list元素一致
//        ArrayList<Integer>list3 = new ArrayList<>(list2);
//        list3.add(4);
//        System.out.println(list3);//输出1，2，3，4
//
//        //避免省略类型，否则任意类型的元素都可以存放，使用时将是一场灾难
//        List list4 = new ArrayList();
//        list4.add("111");
//        list4.add(100);
//    }
//}

//public class Main {
//    public static void main(String[] args) {
//        //创建一个空的列表
//        List<Integer>list1 = new ArrayList<>();
//        List<Integer>list2 = new ArrayList<>(10);
//        list2.add(1);
//        list2.add(2);
//        list2.add(3);
//        List<Integer> list3 = list2.subList(0,1);
//        list3.set(0,188);
//        System.out.println(list2);
//    }
//}

//public class Main {
//    public static void main(String[] args) {
//        //创建一个空的列表
//        List<Integer>list = new ArrayList<>();
//        list.add(1);
//        list.add(2);
//        list.add(3);
//        //使用下标+for遍历
//        for (int i = 0; i < list.size(); i++) {
//            System.out.print(list.get(i)+" ");
//        }
//        System.out.println();
//        //借助foreach遍历
//        for (Integer x:list) {
//            System.out.print(x+" ");
//        }
//        System.out.println();
//        //迭代器
//        Iterator<Integer>it = list.listIterator();
//        while (it.hasNext()){
//            System.out.print(it.next()+" ");
//        }
//        System.out.println();
//    }
//}

//杨辉三角
//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        List<List<Integer>>list = new ArrayList<>();
//        List<Integer>list1 = new ArrayList<>();
//        list1.add(1);
//        list.add(list1);
//        //第一行已经处理完
//        //下面从第二行开始
//        for (int i = 1; i < n; i++) {
//            List<Integer>last = new ArrayList<>();
//            //用来记录上一行
//            List<Integer>middle = new ArrayList<>();
//            //用来记录中间行
//            middle.add(1);
//            //新的一行的第一个值
//            for (int j = 1; j < i; j++) {
//                last = list.get(i-1);
//                middle.add(last.get(j)+last.get(j-1));
//            }
//            middle.add(1);
//            //新的一行的最后一个值
//            list.add(middle);
//        }
//        for (List x:list) {
//            System.out.println(x);
//        }
//
//    }
//}

//移除元素
//class Solution {
//    public int removeElement(int[] nums, int val) {
//        List<Integer> list = new ArrayList<>();
//        int size = nums.length;
//        for (int i = 0; i < size; i++) {
//            list.add(nums[i]);
//        }
//        while (list.contains(val)) {
//            list.remove(new Integer(val));
//            size--;
//        }
//        for (int i = 0; i < size; i++) {
//            nums[i] = list.get(i);
//        }
//        return size;
//    }
//}

//class Solution {
//    public int removeDuplicates(int[] nums) {
//        int size = nums.length;
//        int kk = 1;
//        int cc = 1;
//        if (size==0){
//            return size;
//        }
//
//        for (kk = 1; kk < size;kk++) {
//            if (nums[kk] != nums[kk-1]){
//                nums[cc] = nums[kk];
//                cc++;
//            }
//        }
//        return cc;
//    }
//}

//class Main {
//    public static void merge(int[] nums1, int m, int[] nums2, int n) {
//        while(m>=1 && n>=1){
//           if (nums1[m-1]>nums2[n-1]){
//               nums1[m+n-1] = nums1[m-1];
//               m--;
//           }else {
//               nums1[m+n-1] = nums2[n-1];
//               n--;
//           }
//        }
//        while(m>=1){
//            nums1[m+n-1] = nums1[m-1];
//            m--;
//        }
//        while (n>=1){
//            nums1[m+n-1] = nums2[n-1];
//            n--;
//        }
//    }
//
//    public static void main(String[] args) {
//        int[] n1={1,2,3,0,0,0};
//        int[] n2={4,5,6};
//        int n = 3;
//        int m = 3;
//        merge(n1, m, n2, n);
//        for (int i = 0; i < n1.length; i++) {
//            System.out.println(n1[i]);
//        }
//    }
//}

public class MyArraylist {

    public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 10;

    public MyArraylist() {
        this.elem = new int[DEFAULT_SIZE];
    }

    /**
     * 打印顺序表:
     *   根据usedSize判断即可
     */
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.println(this.elem[i]+" ");
        }
    }

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        //扩容
        if (isFull()){
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
        }
        this.elem[usedSize] = data;
        this.usedSize++;
    }

    /**
     * 判断当前的顺序表是不是满的！
     * @return true:满   false代表空
     */
    public boolean isFull() {
        if (this.elem.length == this.usedSize){
           return true;
        }else {
            return false;
        }
    }


    private boolean checkPosInAdd(int pos) {
        if (pos>=0 && pos<=this.usedSize) {
            return true;//合法
        }else {
            return false;
        }
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        if (checkPosInAdd(pos)){
            System.out.println("位置不合法");
            return;
        }
        if (isFull()){
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
        }
        for (int i = this.usedSize-1; i >=pos ; i--) {
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {

        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {

        return -1;
    }

    // 获取 pos 位置的元素
    public int get(int pos) {

    }

    private boolean isEmpty() {

    }

